package leetcode.code0140;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 执行用时：1 ms, 在所有 Java 提交中击败了95.25%的用户
 *
 * 内存消耗：36.4 MB, 在所有 Java 提交中击败了85.09%的用户
 *
 * 通过测试用例：26 / 26
 */
public class Solution extends Solution140 {

	Node root;
	int Len;

	class Node {

		Node[] characters;
		boolean isEnd;

		public Node() {
			this.characters = new Node[26];
		}

		public void add(String word) {
			Node node = root;
			for (int i = 0; i < word.length(); i++) {
				int index = word.charAt(i) - 'a';
				if (node.characters[index] == null) {
					node.characters[index] = new Node();
				}
				node = node.characters[index];
			}
			node.isEnd = true;
		}
	}

	@Override
	public List<String> wordBreak(String s, List<String> wordDict) {
		this.Len = s.length();
		this.root = new Node();
		for (String word : wordDict) {
			root.add(word);
		}
		char[] string = s.toCharArray();
		Map<Integer, List<String>> dp = new HashMap<>();
		dp.put(this.Len, null);
		return this.f(string, 0, dp);
	}

	private List<String> f(char[] string, int index, Map<Integer, List<String>> dp) {
		if (index == this.Len) {
			return null;
		}
		if (dp.containsKey(index)) {
			return dp.get(index);
		}
		Node node = root;
		List<String> ans = new ArrayList<>();
		for (int i = index; i < this.Len; i++) {
			int c = string[i] - 'a';
			if (node.characters[c] == null) {
				break;
			} else {
				node = node.characters[c];
				if (node.isEnd) {
					String word = new String(string, index, i - index + 1);
					int next = i + 1;
					List<String> list = this.f(string, next, dp);
					if (list != null) {
						for (String sub : list) {
							StringBuffer subSb = new StringBuffer(word);
							subSb.append(' ').append(sub);
							ans.add(subSb.toString());
						}
					} else if (next == this.Len) {
						StringBuffer subSb = new StringBuffer(word);
						ans.add(subSb.toString());
					}
				}
			}
		}
		dp.put(index, ans);
		return ans;
	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
